/**
 * @a https://leetcode.cn/problems/surrounded-regions/description/
 */

#include "../../common.h"


class Solution {
    int row;
    int col;
    static const int dx[4];
    static const int dy[4];
    vector<vector<bool>> visited;
private:
    void bfs(vector<vector<char>>& board, int i, int j){
        if(board[i][j] != 'O') return;
        queue<pair<int,int>> que;
        que.push({i,j});
        visited[i][j] = true;
        board[i][j] = 'R';
        while(que.size()){
            auto [a,b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i){
                int x = a + dx[i];
                int y = b + dy[i];
                if(x >= 0 && x < row && y >= 0 && y < col && visited[x][y] == false && board[x][y] == 'O'){
                    que.push({x,y});
                    visited[x][y] = true;
                    board[x][y] = 'R';
                }
            }
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        row = board.size();
        col = board[0].size();
        visited.resize(row);
        for(auto& line:visited){
            line.resize(col, false);
        }
        for(int i = 0; i < col; ++i){
            if(board[0][i] == 'O') bfs(board,0,i);
            if(board[row - 1][i] == 'O') bfs(board, row - 1, i);
        }

        for(int i = 1; i < row - 1; ++i){
            if(board[i][0] == 'O') bfs(board, i, 0);
            if(board[i][col - 1] == 'O') bfs(board, i, col - 1);
        }

        for(auto& line : board){
            for(auto& item : line){
                if(item == 'O') item = 'X';
                else if(item == 'R') item = 'O';
            }
        }
    }
};
const int Solution::dx[4] = {0,0,1,-1};
const int Solution::dy[4] = {1,-1,0,0};